package com.zjsru.oneDay202212;

import java.util.Arrays;

/**
 * @Author: CookLee
 * @Date: 2022/12/10
 * 堆叠长方体的最大高度
 * cuboids[i] = [widthi, lengthi, heighti]
 * 如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ，你就可以将长方体 i 堆叠在长方体 j 上
 *
 * 输入：cuboids = [[50,45,20],[95,37,53],[45,23,12]]
 * 输出：190
 * 解释：
 * 第 1 个长方体放在底部，53x37 的一面朝下，高度为 95 。
 * 第 0 个长方体放在中间，45x20 的一面朝下，高度为 50 。
 * 第 2 个长方体放在上面，23x12 的一面朝下，高度为 45 。
 * 总高度是 95 + 50 + 45 = 190 。
 *
 * 输入：cuboids = [[38,25,45],[76,35,3]]
 * 输出：76
 * 解释：
 * 无法将任何长方体放在另一个上面。
 * 选择第 1 个长方体然后旋转它，使 35x3 的一面朝下，其高度为 76 。
 *
 */
public class MaxHeight {
    
    public int maxHeight(int[][] cuboids) {
        int n = cuboids.length;
        for (int[] nums : cuboids) {
            //对每个一维数组内的数进行排序
            Arrays.sort(nums);
        }
        //对每一个长方体的三边长度加起来排序
        Arrays.sort(cuboids, (a, b) -> (a[0] + a[1] + a[2]) - (b[0] + b[1] + b[2]));
        int ans = 0;
        //定义一个dp 存储一个每次叠加的height值
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            //存储每一个长方体的height
            dp[i] = cuboids[i][2];
            //满足题意要求，每一条边都需要大于另一个长方体对应的边
            for (int j = 0; j < i; j++) {
                if (cuboids[i][0] >= cuboids[j][0] && cuboids[i][1] >= cuboids[j][1] &&
                        cuboids[i][2] >= cuboids[j][2]) {
                    //可以叠加时，对比长度，由于已经由大到小排过序了，每次遍历考虑加起来最大值即可。遍历后即获取叠加后的最大值
                    dp[i] = Math.max(dp[j] + cuboids[i][2], dp[i]);
                }
            }
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }
    
    public static void main(String[] args) {
        MaxHeight maxHeight = new MaxHeight();
        int[][] cuboids = new int[][] {{50, 45, 20}, {95, 37, 53}, {45, 23, 12}};
        System.out.println(maxHeight.maxHeight(cuboids));
    }
}
